package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

public class _12_判断二叉树是否为平衡二叉树 {

    private static class TreeNodeInfo{

        int height;
        boolean isBalance;

        public TreeNodeInfo(int height, boolean isBalance) {
            this.height = height;
            this.isBalance = isBalance;
        }
    }

    public static boolean isBalanceTree(TreeNode treeNode) {

        return reversal(treeNode).isBalance;
    }

    /**
     * 如果在递归中要返回多个值，使用类作为返回值
     * @param treeNode
     * @return
     */
    public static TreeNodeInfo reversal(TreeNode treeNode) {

        if (treeNode == null) {

            return new TreeNodeInfo(0,true);
        }

        TreeNodeInfo leftTreeNodeInfo = reversal(treeNode.left);
        if (!leftTreeNodeInfo.isBalance) {

            return leftTreeNodeInfo;
        }
        TreeNodeInfo rightTreeNodeInfo = reversal(treeNode.right);
        if (!rightTreeNodeInfo.isBalance) {

            return rightTreeNodeInfo;
        }

        if (Math.abs(leftTreeNodeInfo.height - rightTreeNodeInfo.height) > 1) {

            leftTreeNodeInfo.isBalance = false;
            return leftTreeNodeInfo;
        }

        leftTreeNodeInfo.height = Math.max(leftTreeNodeInfo.height,rightTreeNodeInfo.height) + 1;

        return leftTreeNodeInfo;
    }

    public static void main(String[] args) {

        TreeNode t1 = new TreeNode(1);
        t1.left = new TreeNode(2);
        t1.left.left = new TreeNode(4);
        t1.left.left.left = new TreeNode(8);
        t1.left.left.right = new TreeNode(9);
        t1.left.right = new TreeNode(5);
        t1.left.right.left = new TreeNode(10);
        t1.right = new TreeNode(3);
//        t1.right.left = new TreeNode(6);
        t1.right.right = new TreeNode(7);

        System.out.println(isBalanceTree(t1));

    }
}
